Information transmitted over a communication channel, including a recorder tape, is generally received as a combination of the original information and a noise component. Integrity of the information content is substantially entirely preserved when the signal to noise ratio of the system is large. Accordingly, refinements in design and realization of the appropriate hardware can increase the probability of error-free transmission, theoretically up to the limits imposed by the channel itself. In order to minimize the effect of intrinsic channel limitations, various techniques are employed which ultimately require a compromise between bandwidth and information transfer rate. Various limitations imposed on the channel bandwidth, information rate, and the degree of complexity of receiving and transmitting apparatus contribute to a probable error rate.
Although redundancy is a common element among these techniques, mere repetition exacts a heavy penalty in transmission rate. For example, a single repetition reduces the information rate 50 percent and a second repetition (to implement majority logic) reduces the information rate by 662/3 percent. Other means for insuring message integrity have employed sophisticated coding techniques which permit the detection, location, and correction of errors. Among the desiderata of these coding techniques are high information rate and a capability of correcting multiple errors within any given codeword of transmitted data.
In this context a codeword results from encoding operations performed upon the elements of the original data comprising k bits to yield an encoded word ("codeword") of information having k information bits and r check bits. The encoded redundancy in the form of r check bits is then available during the decoding operations to detect and correct errors in the codeword (including all k+r bits) up to some limit or merely to detect errors up to some larger limit.
Many such codes, having distinct mathematical properties, have been studied and mathematically efficient decoding procedures have been devised, but reduction to practice with concomitant efficiency requires a special purpose computer. For example, certain classes of codes are founded on association of each information element of a codeword with an element of a Galois field.
Very briefly, the Galois field is a finite field, the elements of which may be represented as polynomials in a particular primitive field element, with coefficients in the prime subfield. The locations of errors and the true value of the erroneous information elements are determined after constructing certain polynomials defined on the Galois field and finding the roots of these polynomials. A decoder is therefore required which has the capability of performing Galois field arithmetic.
Of the error correcting codes, a particular class of such codes, separately described by Bose, Chaudhuri and Hocquenhem (thu "BCH" codes), are capable of multiple error correction. Special cases of such codes are the Reed-Solomon (RS) Codes with respect to which the present invention will be described.
One approach to the problem of sufficiently high speed error correction of BCH encoded data was described in terms of an algorithm published in Berlekamp, Algebraic Coding Theory (McGraw-Hill, 1968). Prior art employment of the aforesaid algorithm has utilized in one instance a general purpose digital computer controlling an essentially peripheral arithmetic unit implementing Galois field manipulation. Certain prior art arithmetic units have used large stored tables to implement inversions appearing in decoding procedures.
The Berlekamp patent discloses a computer for implementing Galois field arithmetic and algebra. The computer has fewer components, fewer data paths, and higher speed than a general purpose digital computer employed for this purpose. It includes three distinct sub-structures such that arithmetic operations upon data are implemented in an arithmetic unit substructure, memory addressing for such arithmetic unit are separately effected in an address generator substructure, and each said substructure is controlled by a control unit substructure, whereby such substructures are capable of synchronous concurrent operation.
The Berlekamp patent includes a review of the salient aspects of coding theory, applicable to nonbinary BCH codes in general and to RS codes in particular. As a general reference, the text cited above, Algebraic Coding Theory, is recommended. In a binary realization, such codes may be regarded as having three principal positive integer parameters, n, m, and t, where n is the total length in m-bit characters of a word of encoded information, and n=2.sup.m -1 and t is the error correcting capability of the code. Assuming no fewer than 2t redundant characters or check characters such a codeword is capable of providing sufficient informational redundancy to detect and correct any set of t or fewer independent errors within the codeword of encoded information, or to correct any set of 2t or fewer independent erasures. An erasure may be defined as an error of known location within the received codeword.
The properties of an algebraic finite field may be summarized briefly. For the purposes of the present invention, a field may be informally defined as a set of elements including the null element, 0, and the unit element, 1, upon which are defined operations of addition, multiplication and division. Addition and multiplication are associative and commutative and multiplication is distributive with respect to addition. Every element of the field has a unique negative such that the negative of a given element summed with that given element itself yields the null or 0. Further, every nonzero element has a unique reciprocal such that the product of such an element with its reciprocal yields the unit element, 1. The elements comprising the field may be considered symbolic representations of binary or ternary or q-ary numbers. The description of the invention will be understood best in terms of a field of characteristic two.
The general finite field is called the Galois field and is specified by two parameters, a prime p, and an integer m, whereby GF(p.sup.m) describes a unique finite field (the Galois field of order p.sup.m) having p.sup.m elements. In such a field all operations between elements comprising the field yield results which are again elements of the field. For example, the operation of addition carried out on elements of the finite field GF(2) is defined, modulo 2, according to relations which do not admit of a "carry". Thus, the binary addition tables are: 0+1=1+0=1 and 0+0=1+1=0. Arithmetically, this is a "carry-less" addition, sometimes referred to as half addition and more commonly denoted as the exclusive-OR (XOR). It is apparent that absence of a carry thereby limits the magnitude of the resulting sum to the finite field.
The mathematical basis of Reed-Solomon codes and decoding thereof, as discussed in greater detail in Chapter 10 of Algebraic Coding Theory is as follows:
Let .alpha. be a primitive element in GF(2.sup.m). The code's generator polynomial is defined by ##EQU1## where d is the code's designed distance. The block length of the Reed-Solomon code is n=2.sup.m -1. The codewords consist of all polynomials of degrees&lt;n which are multiples of g(x).
Let C(x) be the transmitted codeword, ##EQU2## If the channel noise adds to this codeword the error pattern ##EQU3## then the received word is ##EQU4##
The received codeword may be passed through a re-encoder (also known as a syndrome generator) which produces as its output the remainder of the polynomial division EQU S(x)=Remainder[R(x)/g(x)]=Remainder[E(x)/g(x)]
from which may be derived the weighted power-sum symmetric functions defined by EQU S.sub.i =S(.alpha..sup.i)=E(.alpha..sup.i)
Since C(x) is a multiple of g(x), it follows that for i=f, f+1, . . . f+d-2, C(.alpha..sup.i)=0, whence EQU S.sub.i =R(.alpha..sup.i)i=f,f+1, . . . f+d-2
The generating function of the S's may be defined by ##EQU5##
In order to correct the errors, the decoder may find the corresponding error locations and error values. If ##EQU6## then the jth error location may be defined as EQU X.sub.j =.alpha..sup.e.sbsp.j
where the e.sub.j are the unique integers such that EQU E.sub.e.sbsb.j .noteq.0
Erasure locations may be similarly associated with field elements and the corresponding values of errata may be defined as EQU Y.sub.j =E.sub.e.sbsb.j
To determine the unknown X's and Y's, it is useful to define these polynomials:
Error locator polynomial EQU .sigma.(z)=.pi.(1-X.sub.i z) EQU X.sub.i =error locations.
Erasure locator polynomial EQU .lambda.(z)=.pi.(1-X.sub.i z) EQU X.sub.i =erasure locations.
Errata locator polynomial EQU .rho.(z)=.sigma.(z).multidot..lambda.(z)
Errata evaluator polynomial ##EQU7##
To find the X's and Y's, the decoder first multiplies S (z) by .lambda.(z) to obtain the modified sydrome generating function EQU T(z)=S(z).multidot..lambda.(z)
The unknown errata evaluator polynomial and the unknown error locator polynomial are related by the key equation, EQU T(z).sigma.(z)=.omega.(z)modz.sup.d
Given T(z), low-degree solutions of .sigma.(z) and .omega.(z) may be found by solving this key equation using the iterative algorithm presented in Algebraic Coding Theory, and later described more succinctly by Sugiyama, et al., A Method For Solving Key Equations for Decoding Goppa Codes, Information & Control, Vol. 27, No. 1, January 1975, pp 87-99.
After the coefficients of .sigma.(z) are known, the decoder may evaluate the polynomials .sigma.(1), .sigma.(.alpha..sup.-1), .sigma.(.alpha..sup.-2), .sigma.(.alpha..sup.-3), . . . ##EQU8## If .sigma.(.alpha..sup.-i).noteq.0, then the received character at location .alpha..sup.i is presumed correct (unless erased). If .sigma.(.alpha..sup.-i)=0 or if .lambda.(.alpha..sup.-i)=0, then .alpha..sup.i is an errata location, and the received character at that position should be corrected by the value given in Eq. (10.32) of Algebraic Coding Theory: ##EQU9##